package cn.hdr.train.lc;

import cn.hdr.train.bean.ListNode;
import cn.hdr.train.bean.TreeNode;

import java.util.*;

/**
 * @date: 2021-04
 */
public class LCTest2104 {

    /**
     * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     * <p>
     *  
     * <p>
     * 示例：
     * <p>
     * 输入："Let's take LeetCode contest"
     * 输出："s'teL ekat edoCteeL tsetnoc"
     *  
     * <p>
     * 提示：
     * <p>
     * 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
     */
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        int start = 0;
        for (int i = 0; i < arr.length; i++) {
            char cur = arr[i];
            if (cur == ' ') {
                supportReverseWords(arr, start, i - 1);
                start = i + 1;
            }
        }

        supportReverseWords(arr, start, arr.length - 1);
        return new String(arr);

    }

    private void supportReverseWords(char[] arr, int start, int end) {
        for (; start < end; start++, end--) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    }


    /**
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
     * <p>
     * 你可以认为每种硬币的数量是无限的。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：coins = [1, 2, 5], amount = 11
     * 输出：3
     * 解释：11 = 5 + 5 + 1
     */
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[] varr = new int[amount + 1];
        Arrays.fill(varr, -1);
        for (int m : coins) {
            if (m <= amount) {
                varr[m] = 1;
            }
        }

        for (int i = 1; i <= amount; i++) {
            if (varr[i] == -1) {
                int min = Integer.MAX_VALUE;
                for (int coin : coins) {
                    if (i > coin && varr[i - coin] != -1) {
                        min = Math.min(min, varr[i - coin] + 1);
                    }
                }
                varr[i] = min == Integer.MAX_VALUE ? -1 : min;
            }
        }

        return varr[amount];
    }

    /**
     * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 
     * <p>
     *  
     * <p>
     * 示例 1:
     * <p>
     * 输入: amount = 5, coins = [1, 2, 5]
     * 输出: 4
     * 解释: 有四种方式可以凑成总金额:
     * 5=5
     * 5=2+2+1
     * 5=2+1+1+1
     * 5=1+1+1+1+1
     * 示例 2:
     * <p>
     * 输入: amount = 3, coins = [2]
     * 输出: 0
     * 解释: 只用面额2的硬币不能凑成总金额3。
     * 示例 3:
     * <p>
     * 输入: amount = 10, coins = [10]
     * 输出: 1
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int x = coin; x < amount + 1; ++x) {
                dp[x] += dp[x - coin];
            }
        }
        return dp[amount];
    }

    /**
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * <p>
     * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     * <p>
     *  
     * 示例 1：
     * <p>
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     * <p>
     * 示例 2：
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * <p>
     * 示例 3：
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     *  
     * <p>
     * 提示：
     * 1 <= nums.length <= 2500
     * -104 <= nums[i] <= 104
     *  
     * <p>
     * 进阶：
     * 你可以设计时间复杂度为 O(n2) 的解决方案吗？
     * 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }

    /**
     * 这道题的方法二，原题解写的不太容易理解，试着在这里再解释一遍：
     * <p>
     * 无序列表最关键的一句在于： 数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值，即在数组 1,2,3,4,5,6中长度为3的上升子序列可以为 1,2,3也可以为 2,3,4等等但是d[3]=3，即子序列末尾元素最小为3。
     * <p>
     * 无序列表解释清了数组d的含义之后，我们接着需要证明数组d具有单调性，即证明i<j时，d[i]<d[j]，使用反证法，假设存在k<j时，d[k]>d[j]，但在长度为j，
     * 末尾元素为d[j]的子序列A中，将后j-i个元素减掉，可以得到一个长度为i的子序列B，其末尾元素t1必然小于d[j]（因为在子序列A中，t1的位置上在d[j]的后面），
     * 而我们假设数组d必须符合表示长度为 i 的最长上升子序列的末尾元素的最小值，此时长度为i的子序列的末尾元素t1<d[j]<d[k]，即t1<d[k]，所以d[k]不是最小的，与题设相矛盾，因此可以证明其单调性
     * <p>
     * 无序列表证明单调性有两个好处：1.可以使用二分法；2.数组d的长度即为最长子序列的长度；
     */
    public int lengthOfLIS1(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }
        int[] d = new int[n + 1];
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }

    /**
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
     * <p>
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     *  
     * <p>
     * 示例 1：
     * 输入："abc"
     * 输出：3
     * 解释：三个回文子串: "a", "b", "c"
     * <p>
     * 示例 2：
     * 输入："aaa"
     * 输出：6
     * <p>
     * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
     */


    public int countSubstrings(String s) {
        char[] arr = s.toCharArray();
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= i; j++) {
                count += isPlalindrome(arr, j, i);
            }
        }
        return count;
    }

    public int isPlalindrome(char[] arr, int start, int end) {
        int lm = (start + end) / 2;
        int rm = (start + end) - lm;
        for (; start <= lm; lm--, rm++) {
            if (arr[lm] != arr[rm]) {
                return 0;
            }
        }
        return 1;
    }

    public int countSubstrings1(String s) {
        char[] arr = s.toCharArray();
        int count = 0;

        //单数回文
        for (int i = 0; i < arr.length; i++) {
            for (int l = i, r = i; l >= 0 && r < arr.length; l--, r++) {
                if (arr[l] == arr[r]) {
                    count++;
                } else {
                    break;
                }
            }
        }

        //双数回文
        for (int i = 0; i < arr.length - 1; i++) {
            for (int l = i, r = i + 1; l >= 0 && r < arr.length; l--, r++) {
                if (arr[l] == arr[r]) {
                    count++;
                } else {
                    break;
                }
            }
        }
        return count;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }

        return ret;
    }

    /**
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * <p>
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
     * <p>
     * 说明：不允许修改给定的链表。
     * <p>
     * 进阶：
     * <p>
     * 你是否可以使用 O(1) 空间解决此题？
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null) {
            slow = slow.next;
            fast = fast.next == null ? null : fast.next.next;

            if (fast != null && slow == fast) {
                //说明有环
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

    /**
     * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
     * <p>
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     * <p>
     * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * 示例:
     * <p>
     * 输入: [1,2,3,0,2]
     * 输出: 3
     * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     */
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        inArr = new Integer[prices.length];
        return maxProfitSupport(prices, 0, 0);
    }

    Integer[] inArr;

    public int maxProfitSupport(int[] prices, int start, int status) {
        if (prices.length - 1 < start) {
            return 0;
        }

        int money;
        if (status == 0) {
            if (inArr[start] != null) {
                money = inArr[start];
            } else {
                //买入
                int money1 = -prices[start] + maxProfitSupport(prices, start + 1, 1);
                //不买
                int money2 = maxProfitSupport(prices, start + 1, 0);
                money = Math.max(money1, money2);

                inArr[start] = money;
            }
        } else {
            //卖出
            int money1 = prices[start] + maxProfitSupport(prices, start + 2, 0);
            //不卖出
            int money2 = maxProfitSupport(prices, start + 1, 1);
            money = Math.max(money1, money2);
        }

        return money;
    }

    /**
     * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
     * <p>
     * 示例 1 :
     * <p>
     * 输入:nums = [1,1,1], k = 2
     * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
     */
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            int sonArrLength = nums.length - i;
            int last = nums[i];
            if (last == k) {
                sum++;
            }
            for (int j = 1; j < sonArrLength; j++) {
                last += nums[j + i];
                if (last == k) {
                    sum++;
                }
            }

        }
        return sum;
    }

    public int subarraySum2(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        for (int num : nums) {
            pre += num;
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    /**
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     * <p>
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
     * 输出：true
     */
    public boolean exist(char[][] board, String word) {
        char start = word.charAt(0);

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == start) {
                    Set<String> load = new HashSet<>();
                    load.add(i + "," + j);
                    if (existSupport(board, word, 1, i, j, load)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    public boolean existSupport(char[][] board, String word, int index, int i, int j, Set<String> load) {
        if (word.length() == index) {
            return true;
        }

        if (i - 1 >= 0 && board[i - 1][j] == word.charAt(index) && !load.contains((i - 1) + "," + j)) {
            Set<String> loadNew = new HashSet<>(load);
            loadNew.add((i - 1) + "," + j);
            if (existSupport(board, word, index + 1, i - 1, j, loadNew)) {
                return true;
            }
        }

        if (i + 1 < board.length && board[i + 1][j] == word.charAt(index) && !load.contains((i + 1) + "," + j)) {
            Set<String> loadNew = new HashSet<>(load);
            loadNew.add((i + 1) + "," + j);
            if (existSupport(board, word, index + 1, i + 1, j, loadNew)) {
                return true;
            }
        }

        if (j + 1 < board[i].length && board[i][j + 1] == word.charAt(index) && !load.contains(i + "," + (j + 1))) {
            Set<String> loadNew = new HashSet<>(load);
            loadNew.add(i + "," + (j + 1));
            if (existSupport(board, word, index + 1, i, j + 1, loadNew)) {
                return true;
            }
        }

        if (j - 1 >= 0 && board[i][j - 1] == word.charAt(index) && !load.contains(i + "," + (j - 1))) {
            Set<String> loadNew = new HashSet<>(load);
            loadNew.add(i + "," + (j - 1));
            if (existSupport(board, word, index + 1, i, j - 1, loadNew)) {
                return true;
            }
        }
        return false;
    }

    public boolean exist2(char[][] board, String word) {
        char[] arr = word.toCharArray();
        Stack<int[]> queue = new Stack<>();
        LinkedList<String> linkedList = new LinkedList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                queue.add(new int[]{i, j, 0});
                linkedList.clear();
                int index = 0;
                while (!queue.isEmpty()) {
                    int[] zb = queue.pop();
                    int x = zb[0];
                    int y = zb[1];
                    int v = zb[2];
                    if (index > v) {
                        index = v;
                        linkedList.removeLast();
                    }
                    if (board[x][y] == arr[v] && !linkedList.contains(x + "," + y + "," + arr[v])) {
                        linkedList.add(x + "," + y + "," + arr[v]);
                        System.out.println(Arrays.toString(linkedList.toArray()));
                        index++;
                        if (++v == word.length()) {
                            return true;
                        }

                        if (x - 1 >= 0) {
                            queue.add(new int[]{x - 1, y, v});
                        }
                        if (y - 1 >= 0) {
                            queue.add(new int[]{x, y - 1, v});
                        }
                        if (x + 1 < board.length) {
                            queue.add(new int[]{x + 1, y, v});
                        }
                        if (y + 1 < board[x].length) {
                            queue.add(new int[]{x, y + 1, v});
                        }
                    }
                }
            }
        }
        return false;
    }

    /**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 假设一个二叉搜索树具有如下特征：
     * <p>
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     */
    public boolean isValidBST(TreeNode root) {
        return preTree(root);
    }

    private TreeNode last = null;

    public boolean preTree(TreeNode root) {
        if (root.left != null) {
            if (!preTree(root.left)) {
                return false;
            }
        }

        if (last != null && root.val <= last.val) {
            return false;
        }
        last = root;

        if (root.right != null) {
            if (!preTree(root.right)) {
                return false;
            }
        }
        return true;
    }

    public boolean isValidBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();

            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;

            root = root.right;
        }
        return true;
    }

    /**
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
     */
    public int numTrees(int n) {
        int[] db = new int[n + 1];
        db[0] = 1;
        db[1] = 1;
        for (int i = 2; i <= n; i++) {
            int v = 0;
            for (int j = 1; j <= i; j++) {
                int m = db[j - 1] * db[i - j];
                v += m;
            }
            db[i] = v;
        }
        return db[n];
    }

    /**
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * <p>
     * 提醒一下，二叉搜索树满足下列约束条件：
     * <p>
     * 节点的左子树仅包含键 小于 节点键的节点。
     * 节点的右子树仅包含键 大于 节点键的节点。
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        convertBSTSupport(root);

        return root;
    }

    private int preNodeVal = 0;

    public void convertBSTSupport(TreeNode root) {
        if (root.right != null) {
            convertBSTSupport(root.right);
        }

        root.val += preNodeVal;

        preNodeVal = root.val;

        if (root.left != null) {
            convertBSTSupport(root.left);
        }
    }


    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 || j == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }

            }
        }

        return dp[m][n];
    }


    /**
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * <p>
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     * <p>
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
     * <p>
     * 示例 2：
     * 输入：nums = [0]
     * 输出：[[],[0]]
     *  
     * <p>
     * 提示：
     * 1 <= nums.length <= 10
     * -10 <= nums[i] <= 10
     * nums 中的所有元素 互不相同
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> listList = new ArrayList<>();
        for (int num : nums) {
            List<List<Integer>> addlistList = new ArrayList<>();
            addlistList.add(Collections.singletonList(num));

            for (List<Integer> list : listList) {
                addlistList.add(addElement(list, num));
            }
            listList.addAll(addlistList);
        }
        listList.add(new ArrayList<>());
        return listList;
    }

    private List<Integer> addElement(List<Integer> list, Integer value) {
        List<Integer> newList = new ArrayList<>(list.size() + 1);
        newList.addAll(list);
        newList.add(value);
        return newList;
    }

    /**
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     * <p>
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     * <p>
     * abc     def
     * ghi      jkl     mno
     * pqrs     tuv     wsyz
     * <p>
     * <p>
     * "2365"
     * ["admj","admk","adml","adnj","adnk","adnl","adoj","adok","adol",
     * "aemj","aemk","aeml","aenj","aenk","aenl","aeoj","aeok","aeol",
     * "afmj","afmk","afml","afnj","afnk","afnl","afoj","afok","afol",
     * "bdmj","bdmk","bdml","bdnj","bdnk","bdnl","bdoj","bdok","bdol",
     * "bemj","bemk","beml","benj","benk","benl","beoj","beok","beol",
     * "bfmj","bfmk","bfml","bfnj","bfnk","bfnl","bfoj","bfok","bfol",
     * "cdmj","cdmk","cdml","cdnj","cdnk","cdnl","cdoj","cdok","cdol",
     * "cemj","cemk","ceml","cenj","cenk","cenl","ceoj","ceok","ceol",
     * "cfmj","cfmk","cfml","cfnj","cfnk","cfnl","cfoj","cfok","cfol"]
     */
    public List<String> letterCombinations2(String digits) {
        char[] chars = digits.toCharArray();
        char[][] arr2 = new char[][]{{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 's', 'y', 'z'}};

        int size = 1;
        for (char aChar : chars) {
            int index = aChar - '2';
            char[] dArr = arr2[index];
            size *= dArr.length;
        }

        List<char[]> builderList = new ArrayList<>();
        for (int j = 0; j < size; j++) {
            builderList.add(new char[chars.length]);
        }

        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - '2';
            char[] dArr = arr2[index];
            for (int j = 0, k = 0; j < size; j++) {
                char[] temp = builderList.get(j);
                temp[i] = dArr[k];

                if (k == dArr.length - 1) {
                    k = 0;
                } else {
                    k++;
                }
            }
        }

        List<String> list = new ArrayList<>();
        for (char[] sonChar : builderList) {
            list.add(new String(sonChar));
        }
        return list;
    }


    public void printfList(List<char[]> builderList) {
        List<String> list = new ArrayList<>();
        for (char[] sonChar : builderList) {
            list.add(new String(sonChar));
        }
        System.out.println(list.toString());
    }

    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }

    /**
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     * <p>
     * 示例:
     * <p>
     * 输入: [1,2,3]
     * 输出:
     * [
     * [1,2,3],
     * [1,3,2],
     * [2,1,3],
     * [2,3,1],
     * [3,1,2],
     * [3,2,1]
     * ]
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> all = new ArrayList<>();
        Integer[] copy = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            copy[i] = nums[i];
        }
        dfsPermute(all, copy, new ArrayList<>(nums.length));
        return all;
    }

    private void dfsPermute(List<List<Integer>> all, Integer[] nums, List<Integer> preList) {
        if (preList.size() == nums.length) {
            all.add(preList);
        }

        for (int i = 0; i < nums.length; i++) {
            Integer num = nums[i];
            if (num != null) {
                List<Integer> list = new ArrayList<>(nums.length);
                list.addAll(preList);
                list.add(nums[i]);

                nums[i] = null;
                dfsPermute(all, nums, list);
                //回溯
                nums[i] = num;
            }
        }
    }


    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     * 示例 2：
     * <p>
     * 输入：intervals = [[1,4],[4,5]]
     * 输出：[[1,5]]
     * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
     *  
     * <p>
     * 提示：
     * <p>
     * 1 <= intervals.length <= 104
     * intervals[i].length == 2
     * 0 <= starti <= endi <= 104
     */
    public int[][] merge(int[][] intervals) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int[] interval : intervals) {
            Integer v1 = interval[0];
            Integer v2 = interval[1];

            Integer num1 = map.getOrDefault(v1, 0);
            map.put(v1, num1 + 1);

            Integer num2 = map.getOrDefault(v2, 0);
            map.put(v2, num2 - 1);
        }

        int stack = 0;
        List<int[]> list = new ArrayList<>();
        int[] temp = new int[2];
        boolean temp0Null = true;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();

            if (temp0Null) {
                temp[0] = key;
                temp0Null = false;
            }

            stack += value;

            if (stack == 0) {
                temp[1] = key;
                //重置
                list.add(temp);
                temp = new int[2];
                temp0Null = true;
            }
        }

        int[][] allRange = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            allRange[i] = list.get(i);
        }
        return allRange;
    }
    public int[][] merge2(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            int L = interval[0], R = interval[1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }



    /**
     * [120,70,140,50,100,130,160,20,55,75,110,119,135,150,200]
     */
    public static void main(String[] args) throws Exception {
        LCTest2104 bean = new LCTest2104();

//        int[][] merge = bean.merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
        int[][] merge = bean.merge(new int[][]{{1, 4}, {4, 4}, {4, 5}});
//        int[][] merge = bean.merge(new int[][]{{1, 4}, {0, 4}});

        for (int[] nums : merge) {
            System.out.println(Arrays.toString(nums));
        }
    }
}